package pers.qianyu.month_202012.date_20201212;

import org.junit.*;

/**
 * 42. 接雨水
 * https://leetcode-cn.com/problems/trapping-rain-water/
 *
 * @author mizzle rain
 * @date 2020-12-12 15:09
 */
public class Trap {
    /**
     * 动态规划解法
     */
    public int trap(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int res = 0;
        // 站在 i 位置，从左往右看，最高的柱子所在的位置的高度为 left[i]
        int[] left = new int[height.length];
        left[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            left[i] = Math.max(left[i + 1], height[i]);
        }
        // 站在 i 位置，从右往左看，最高的柱子所在的位置的高度为 right[i]
        int[] right = new int[height.length];
        right[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            right[i] = Math.max(right[i - 1], height[i]);
        }
        for (int i = 0; i < height.length; i++) {
            if (left[i] > height[i] && right[i] > height[i]) {
                res += Math.min(left[i], right[i]) - height[i];
            }
        }
        return res;
    }

    @Test
    public void test1() {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int result = new Trap().trap(arr);
        System.out.println("result = " + result);
    }
}
